package tree;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BinaryTreeZigzagLevelOrderTraversal103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<List<Integer>> lists = new LinkedList<>();
        LinkedList<TreeNode> q = new LinkedList<>();
        boolean directionLeft = true;
        q.addLast(root);
        while (q.size() > 0) {
            int size = q.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                // 遍历当前层的时候, 始终按照从左到右取出.
                // 技巧是放入结果集的时候, 按顺序放入首部或尾部.
                TreeNode curr = q.pollFirst();
                if (directionLeft) {
                    list.addLast(curr.val);
                } else {
                    list.addFirst(curr.val);
                }
                // 产生下一层的时候, 始终按照从左到右产生
                if (curr.left != null) {
                    q.addLast(curr.left);
                }
                if (curr.right != null) {
                    q.addLast(curr.right);
                }
            }
            directionLeft = !directionLeft;
            lists.add(list);
        }
        return lists;
    }
}
